package com.acwing.partition3;

import java.io.*;
import java.util.*;

/**
 * @author `RKC`
 * @date 2022/5/2 9:20
 */
public class AC255第K小数 {

    private static final int N = 100010;
    private static Node[] tr = new Node[N * 4 + N * 17];
    private static int[] a = new int[N], root = new int[N];
    private static List<Integer> nums = new ArrayList<>();
    private static int n, m, idx = 0;

    private static StreamTokenizer tokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = nextInt(); m = nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = nextInt();
            nums.add(a[i]);
        }
        //离散化
        Collections.sort(nums);
        nums = unique(nums);
        root[0] = build(0, nums.size() - 1);
        //每次插入一个新的数，都是一个新的版本
        for (int i = 1; i <= n; i++) root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
        while (m-- > 0) {
            int l = nextInt(), r = nextInt(), k = nextInt();
            writer.println(nums.get(query(root[r], root[l - 1], 0, nums.size() - 1, k)));
        }
        writer.flush();
    }

    private static int query(int q, int p, int l, int r, int k) {
        if (l == r) return r;
        //tr[tr[q].l].cnt-tr[tr[p].l].cnt 的结果是求出在p之后插入到q这些数之后，有多少个数(cnt)插入了p的左子树, 由于p的内容肯定不能出现在l r之间(p根节点就是root[l-1])，
        //所以cnt就是相当于"存在q左子树里面但不存在于 1到l 之间的数的个数"
        int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt, mid = l + r >> 1;
        if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
        return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
    }

    private static int insert(int p, int l, int r, int x) {
        int q = ++idx;
        //原节点的信息复制过来
        tr[q] = new Node(tr[p].l, tr[p].r, tr[p].cnt);
        if (l == r) {
            tr[q].cnt++;
            return q;
        }
        int mid = l + r >> 1;
        if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
        else tr[q].r = insert(tr[p].r, mid + 1, r, x);
        tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
        return q;
    }

    private static int build(int l, int r) {
        int q = ++idx;
        tr[q] = new Node(l, r, 0);
        if (l == r) return q;
        int mid = l + r >> 1;
        tr[q].l = build(l, mid);
        tr[q].r = build(mid + 1, r);
        return q;
    }

    private static int find(int x) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums.get(mid) < x) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    private static List<Integer> unique(List<Integer> nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            if (i == 0 || !nums.get(i).equals(nums.get(i - 1))) {
                res.add(nums.get(i));
            }
        }
        return res;
    }

    private static class Node {
        //指向左右子树的指针
        private int l, r;
        private int cnt;

        public Node(int l, int r, int cnt) {
            this.l = l;
            this.r = r;
            this.cnt = cnt;
        }
    }

    private static int nextInt() throws IOException {
        tokenizer.nextToken();
        return (int) tokenizer.nval;
    }
}
